#include"erfen.h"
#include "Cmd_Draw.h"
#include "startprogram.h"

using namespace std; 

int di[1000][1000];

inline int pan(int x,int y) //judge the area whether reachable from the view of entrance
{							//1 means wall,2 means it has walked, 3 means it's not accessible, 4 means it's the member of the exit, which means it's a accessible path.
	if(di[x][y]==1||di[x][y]==2||di[x][y]==3) return 0;//not reachable
	else if(di[x][y]==4) return -1;//judge the area whether in the stack of the exit(work with the function of pannum)
	else return 1;//reachable
}
inline int pan1(int x,int y)  //judge the area whether reachable from the view of exit
{							  //1 means wall,4 means it has walked, 3 means it's not accessible,2 means it's the member of the entrance, which means it's a accessible path.
	if(di[x][y]==1||di[x][y]==4||di[x][y]==3) return 0;//not reachable 
	else if(di[x][y]==2) return -1;//judge the area whether in the queue of the entrance(work with the function of pannum1)
	else return 1;//reachable
}
inline int pannum(int x,int y) //return the amount of path can walk.If encountering the member of the exit, return negative number.
{
	if(pan(x,y+1)<0) return -1; 
	if(pan(x+1,y)<0) return -2;
	if(pan(x,y-1)<0) return -3;
	if(pan(x-1,y)<0) return -4;
	return pan(x+1,y)+pan(x,y+1)+pan(x-1,y)+pan(x,y-1);
}
inline int pannum1(int x,int y)//return the amount of path can walk.If encountering the member of the entrance, return negative number.
{
	if(pan1(x,y+1)<0) return -1;
	if(pan1(x+1,y)<0) return -2;
	if(pan1(x,y-1)<0) return -3;
	if(pan1(x-1,y)<0) return -4;
	return pan1(x+1,y)+pan1(x,y+1)+pan1(x-1,y)+pan1(x,y-1);
}
inline void coutdirection(int x,int y,int x1,int y1)
{
	if(x==x1)
	{
		if(y-1==y1) cout<<"LEFT)\n";
		else cout<<"RIGHT)\n";
	} 
	else if(y==y1)
	{
		if(x+1==x1) cout<<"DOWN)\n";
		else cout<<"UP)\n";
	}
}
int entrance::pop1() //pop the member at the last of the entrance(queue)(for search)
{
    if(Size==0) return -1;
    ListNode* temp=tail;
    int a = tail->data;
    tail=tail->before;
    delete temp;
    Size--;
    return a;
}

void entrance::push(int x,int y) //push the Point coordinates(two data) in the entrance(queue)(different with the initial definition of push(only one data))
{
   ListNode* temp = new ListNode(x,y);  
   if (head == NULL) 
   {					   
       head = temp;
       tail = temp;
   }
   else
    tail->next = temp;
    ListNode* p=tail;
	tail = temp;
	tail->before=p;
	Size++;
}

void exit1::push(int x,int y) //push the Point coordinates(two data) in the exit(stack)(different with the initial definition of push(only one data))
{
    ListNode* ptr=new ListNode(x,y);
    ptr->next=head;
    head=ptr;
    Size++;
}

int search(int x,int y,int xn,int yn) //the function to searcn the best direction to reach the object(exit or the latest crossroads) based on the distance(entrance view)
{										//1 means left ,2 means down, 3 means right, 4 means up	
	if(x==xn)
	{
		if(y>yn) 
		{ 	if(pan(x,y-1)) return 3; 
			if(pan(x+1,y)) return 2;   //it's obviously to get more closly to the initial exit if we walk left.
			if(pan(x-1,y)) return 4;
			if(pan(x,y+1)) return 1;
		}
		else 
		{ 	if(pan(x,y+1)) return 1;
			if(pan(x+1,y)) return 2; 
			if(pan(x-1,y)) return 4;
			if(pan(x,y-1)) return 3;
		}
	}
	else if(y==yn) 
	{
		if(x>xn) 
		{	if(pan(x-1,y)) return 4;
			if(pan(x,y+1)) return 1; //it's obviously to get more closly to the initial exit if we walk down.
			if(pan(x,y-1)) return 3;
			if(pan(x+1,y)) return 2;}
		else 
		{	if(pan(x+1,y)) return 2;
			if(pan(x,y+1)) return 1;
			if(pan(x,y-1)) return 3;
			if(pan(x-1,y)) return 4;}
	}
	else if(abs(x-xn)<abs(y-yn)) 
	{
		if(x>xn) {if(pan(x-1,y)) return 4;}
		else {if(pan(x+1,y)) return 2;}
		if(y>yn) {if(pan(x,y-1)) return 3;
				  if(pan(x,y+1)) return 1;}
		else {if(pan(x,y+1)) return 1;
			  if(pan(x,y-1)) return 3;}
		if(x>xn) {if(pan(x+1,y)) return 2;}
		else {if(pan(x-1,y)) return 4;}
	}
	else
	{	
		if(y>yn) { if(pan(x,y-1)) return 3;}
		else {if(pan(x,y+1)) return 1;}
		if(x>xn) {if(pan(x-1,y)) return 4;
				  if(pan(x+1,y)) return 2;}
		else {if(pan(x+1,y)) return 2;
			  if(pan(x-1,y)) return 4;}
		if(y>yn) {if(pan(x,y+1)) return 1;}
		else {if(pan(x,y-1)) return 3;}
	}
	return 0;
}
int search1(int x,int y,int xn,int yn) //the function to searcn the best direction to reach the object(exit or the latest crossroads) based on the distance(entrance view)
{										
	Queue ke;
	if(x==xn)
	{
		if(y>yn) 
		{ 	if(pan1(x,y-1)) return 3;
			if(pan1(x-1,y)) return 4;   //it's obviously to get more closly to the initial entrance if we walk right.
			if(pan1(x+1,y)) return 2;
			if(pan1(x,y+1)) return 1;
		}
		else 
		{ 	if(pan1(x,y+1)) return 1;
			if(pan1(x-1,y)) return 4; 
			if(pan1(x+1,y)) return 2;
			if(pan1(x,y-1)) return 3;
		}
	}
	else if(y==yn) 
	{
		if(x>xn) 
		{	if(pan1(x-1,y)) return 4;
			if(pan1(x,y-1)) return 3; 	//it's obviously to get more closly to the initial entrance if we walk up.
			if(pan1(x,y+1)) return 1;
			if(pan1(x+1,y)) return 2;}
		else 
		{	if(pan1(x+1,y)) return 2;
			if(pan1(x,y-1)) return 3;
			if(pan1(x,y+1)) return 1;
			if(pan1(x-1,y)) return 4;}
	}
	else if(abs(x-xn)<abs(y-yn)) 
	{
		if(x>xn) {if(pan1(x-1,y)) return 4;}
		else {if(pan1(x+1,y)) return 2;}
		if(y>yn) {if(pan1(x,y-1)) return 3;
				  if(pan1(x,y+1)) return 1;}
		else {if(pan1(x,y+1)) return 1;
			  if(pan1(x,y-1)) return 3;}
		if(x>xn) {if(pan1(x+1,y)) return 2;}
		else {if(pan1(x-1,y)) return 4;}
	}
	else
	{	
		if(y>yn) { if(pan1(x,y-1)) return 3;}
		else {if(pan1(x,y+1)) return 1;}
		if(x>xn) {if(pan1(x-1,y)) return 4;
				  if(pan1(x+1,y)) return 2;}
		else {if(pan1(x+1,y)) return 2;
			  if(pan1(x-1,y)) return 4;}
		if(y>yn) {if(pan1(x,y+1)) return 1;}
		else {if(pan1(x,y-1)) return 3;}
	}
	return 0;
}

void move(exit1 &ch,entrance &r) //the function to search the accessible path
{
	while(1)
	{
		int k=1;// the flag to show 3 state:1 means the search should continue, 2 means find the accessible path, 0 means can't find the accessible path
		int add=0;// the flag to judge whether we should explore the crossloads
		while(1)
		{	
			erfennum++;
			int x1=r.getx();
			int y1=r.gety();
			int x2=ch.getx();//get the data of latest crossroads of the exit
			int y2=ch.gety();
			Set_Grapics(y1*2,x1,12); cout<<"*";	
			di[x1][y1]=2;//indiacate this road we had walked
			if(pannum(x1,y1)<0) //indicate that the accessible path is found
			{
				int a=-pannum(x1,y1);
				switch(a) 
				{
					case 1: r.push(x1,y1+1);break;
					case 2: r.push(x1+1,y1);break;
					case 3: r.push(x1,y1-1);break;
					case 4: r.push(x1-1,y1);break;
				}
				k=2;
				break;
			}
			r.setdata(pannum(x1,y1)); //it's the data to show the previous crossroads of the dead end
			if(r.getdata()>1&&add) break; //indicate we find the new crossroads
			if(r.getdata()==0) //indicate we find the dead end
			{
				int x,y;
				while(1)
				{
					erfennum++;
					x=r.getx();
					y=r.gety();
					di[x][y]=0; 
					Set_Grapics(y*2,x,12);cout<<"  ";
					r.pop1();
					if(r.Qsize()==0) {k=0;break;}
					if(r.getdata()!=1) break;
				}
				Set_Grapics(y*2,x,1);
				cout<<"*";
				di[x][y]=3;	//indicate this direction of the crossroads isn't accessible
				if(k) //to avoid empty queue that can't get x,y  
				{
					x=r.getx();
					y=r.gety();
					di[x][y]=0;  
				} 
				break;
			}
			if(abs(y2-y1)+abs(x2-x1)>abs(y2-col-2)+abs(x2-row-2))// to reduce the influence of exit wrong path on the accessible path searcing to increase efficiency
			{
				x2=row-2;
				y2=col-2;
			}
			int a=search(x1,y1,x2,y2);// to get the best direction for search
			switch(a) 
			{
				case 1: r.push(x1,y1+1);break;
				case 2: r.push(x1+1,y1);break;
				case 3: r.push(x1,y1-1);break;
				case 4: r.push(x1-1,y1);break;
			}
			add++;
		}
		if(!k) //the operation of not accessible path
		{
			Set_Grapics(0,row+1,12);
			cout<<"*\n";
			break; 
		}
		if(k==2) //the operation of accessible path
		{
			int n=1;
			int x1,y1,x,y;
			x=r.getx();
			y=r.gety();
			while(ch.Ssize()) //to pop the member of exit until the meeting points
			{
				erfennum++;				
				if(x==ch.getx()&&y==ch.gety()) {ch.pop();break;}
				Set_Grapics(ch.gety()*2,ch.getx(),12);cout<<"  ";
				ch.pop();
			}
			Set_Grapics(y*2,x,12);cout<<"*";
			Set_Grapics(0,row+1,12);
			x=r.getx1();
			y=r.gety1();
			while(1)
			{
				r.pop();
				if(r.Qsize()==0) break;
				x1=r.getx1();
				y1=r.gety1();
				erfennum++;
				cout<<"("<<x<<","<<y<<",";
				coutdirection(x,y,x1,y1);
				x=x1;
				y=y1;
				
			}
			while(ch.Ssize())
			{
				x1=ch.getx();
				y1=ch.gety();
				erfennum++;
				cout<<"("<<x<<","<<y<<",";
				coutdirection(x,y,x1,y1);
				x=x1;
				y=y1;
				ch.pop();
			}
			cout<<"("<<x<<","<<y<<")";
			break;
		}
		add=0;
		while(1)
		{
			erfennum++;
			int x1=ch.getx();
			int y1=ch.gety();
			int x2=r.getx();
			int y2=r.gety();
			Set_Grapics(y1*2,x1,12); cout<<"*";
			di[x1][y1]=4;
			if(pannum1(x1,y1)<0) 
			{	
				int a=-pannum1(x1,y1);
				switch(a) 
				{
					case 1: ch.push(x1,y1+1);break;
					case 2: ch.push(x1+1,y1);break;
					case 3: ch.push(x1,y1-1);break;
					case 4: ch.push(x1-1,y1);break;
				}
				k=2;
				break;
			} 
			ch.setdata(pannum1(x1,y1));
			if(ch.getdata()>1&&add)  break;
			if(ch.getdata()==0)
			{
				int x,y;
				while(1)
				{
					erfennum++;
					x=ch.getx();
					y=ch.gety();
					Set_Grapics(y*2,x,12);cout<<"  ";
					di[x][y]=0;
					ch.pop();
					if(ch.Ssize()==0) {k=0;break;}
					if(ch.getdata()!=1) break;
				}
				Set_Grapics(y*2,x,1); cout<<"*";
				di[x][y]=3;	
				if(k)
				{
					x=ch.getx();
					y=ch.gety();
					di[x][y]=0;	
				}
				break;
			}
			if(abs(y2-y1)+abs(x2-x1)>abs(y2-1)+abs(x2-1))
			{
				x2=1;
				y2=1;
			}
			int a=search1(x1,y1,x2,y2);
			switch(a) 
			{
				case 1: ch.push(x1,y1+1);break;
				case 2: ch.push(x1+1,y1);break;
				case 3: ch.push(x1,y1-1);break;
				case 4: ch.push(x1-1,y1);break;
			}
			add++;
		}
		if(!k)  
		{
			Set_Grapics(0,row+1,12); cout<<"*\n";
			break; 
		}
		if(k==2) //the operation of accessible path
		{
		
			int n=1;
			int x1,y1,x,y;
			x=ch.getx();
			y=ch.gety();
			while(r.Qsize())
			{
				erfennum++;
				if(x==r.getx()&&y==r.gety()) {r.pop1();break;}
				Set_Grapics(r.gety()*2,r.getx(),12);cout<<"  ";
				r.pop1();
			}
			Set_Grapics(y*2,x,12);cout<<"*";
			Set_Grapics(0,row+1,12);
			x=r.getx1();
			y=r.gety1();
			
			while(1)
			{
				r.pop();
				if(r.Qsize()==0) break;
				x1=r.getx1();
				y1=r.gety1();
				erfennum++;
				cout<<"("<<x<<","<<y<<",";
				coutdirection(x,y,x1,y1);
				x=x1;
				y=y1;
				
			}
			while(ch.Ssize())
			{
				x1=ch.getx();
				y1=ch.gety();
				erfennum++;
				cout<<"("<<x<<","<<y<<",";
				coutdirection(x,y,x1,y1);
				x=x1;
				y=y1;
				ch.pop();
			}
			cout<<"("<<x<<","<<y<<")";
			break;
		}
	}
}

void init_erfen()
{
	memcpy(di,map,sizeof(map));
}


